package leetcode.栈队列堆;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 最长有效括号
 *
 * 给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
 *
 * 示例 1:
 *
 * 输入: "(()"
 * 输出: 2
 * 解释: 最长有效括号子串为 "()"
 *
 */
public class Test32最长有效括号 {
    public static int longestValidParentheses(String s) {
        if (s.isEmpty()) {
            return 0;
        }
        int result = 0;
        Deque<Integer> stack = new LinkedList<>();
        /**
         * 如下图：
         *   -1 0 1 2 3 4
         *   *  ( ) ( ( )
         *
         * 合法括号的长度为2，其中之一是下标为0、1的两个括号的组合
         * 要想计算出这个2，其实用它们的下标相减即可，但是1 - 0 = 1 不等于 2
         * 所以需要再往前减一位，即设置一个 -1
         */
        stack.push(-1);

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                // 一旦遇到右括号就要开始计算长度，需要跳过一个进行相减才计算的出正确长度
                stack.pop();
                // 开始计算长度
                if (!stack.isEmpty()) {
                    result = Math.max(result, i - stack.peek());
                } else {
                    // 如果当前栈为空，说明存在不合法的子串，例如：)()
                    // 需要重新设定当前找到的括号的下标为合法的起始下标，好用来准备计算
                    stack.push(i);
                }
            } else {
                // 压入全部的左括号下标，等待使用右括号下标来计算长度
                stack.push(i);
            }
        }
        return result;
    }

    public static void main(String[] args) {
//        String str = "(()";

        //String str = ")())())";

//        String str = "()(())";

//        String str = "(((())))";

//        String str = "()(())";

//        String str = "()(((())";

        String str = ")))";
        System.out.println(longestValidParentheses(str));

    }
}
